#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int minCost(vector<vector<int>>& nums)
    {
        int n = nums.size();
        vector<vector<int>> red(n + 1, vector<int>(3));
        auto green = red;
        auto blue = red;

        for (int i = 1; i <= n; i++)
        {
            red[i][0] = nums[i - 1][0] + min(blue[i - 1][1], green[i - 1][2]);
            blue[i][1] = nums[i - 1][1] + min(red[i - 1][0], green[i - 1][2]);
            green[i][2] = nums[i - 1][2] + min(red[i - 1][0], blue[i - 1][1]);
        }
        return min(red[n][0], min(blue[n][1], green[n][2]));
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(3));
        dp[0][0] = -prices[0];

        for (int i = 1; i < n; i++)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
            dp[i][1] = dp[i - 1][0] + prices[i];
            dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]);
        }
        return max(dp[n - 1][1], dp[n - 1][2]);
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee)
    {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2));
        dp[0][0] = -prices[0];

        for (int i = 1; i < n; i++)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }
        return dp[n - 1][1];
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(3, -0x3f3f3f3f));
        auto g = f;
        f[0][0] = -prices[0];
        g[0][0] = 0;
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j <= 2; j++)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j - 1 >= 0)
                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        }

        int ret = 0;
        for (int i = 0; i < 3; i++)
        {
            ret = max(ret, g[n - 1][i]);
        }
        return ret;
    }
};


class Solution {
public:
    int maxProfit(int k, vector<int>& prices)
    {
        int n = prices.size();
        k = min(k, n / 2);

        vector<vector<int>> f(n, vector<int>(k + 1, -0x3f3f3f3f));
        auto g = f;
        f[0][0] = -prices[0];
        g[0][0] = 0;

        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j <= k; j++)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j - 1 >= 0)
                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        }

        int ret = 0;
        for (int i = 0; i <= k; i++)
        {
            ret = max(ret, g[n - 1][i]);
        }
        return ret;
    }
};

class Solution
{
public:
    int maxSubArray(vector<int>& nums)
    {
        int n = nums.size();
        int sum = nums[0];
        int ret = nums[0];

        for (int i = 1; i < n; ++i)
        {
            sum = max(nums[i], sum + nums[i]);
            ret = max(ret, sum);
        }
        return ret;
    }
};

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);
        int fmax = INT_MIN, gmin = INT_MAX;
        for (int i = 1; i <= n; i++)
        {
            f[i] = max(f[i - 1] + nums[i - 1], nums[i - 1]);
            g[i] = min(g[i - 1] + nums[i - 1], nums[i - 1]);
            fmax = max(fmax, f[i]);
            gmin = min(gmin, g[i]);
        }

        int sum = 0;
        for (auto& e : nums)
            sum += e;

        return sum == gmin ? fmax : max(fmax, sum - gmin);
    }
};

class Solution {
public:
    int maxProduct(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);

        f[0] = g[0] = 1;
        int ret = INT_MIN;
        for (int i = 1; i <= n; ++i)
        {
            if (nums[i - 1] > 0)
            {
                f[i] = max(nums[i - 1], f[i - 1] * nums[i - 1]);
                g[i] = min(nums[i - 1], g[i - 1] * nums[i - 1]);
            }
            else
            {
                f[i] = max(nums[i - 1], g[i - 1] * nums[i - 1]);
                g[i] = min(nums[i - 1], f[i - 1] * nums[i - 1]);
            }
            ret = max(ret, f[i]);
        }
        return ret;

    }
};

class Solution {
public:
    int getMaxLen(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);
        int ret = 0;
        for (int i = 1; i <= n; i++)
        {
            if (nums[i - 1] > 0)
            {
                f[i] = f[i - 1] + 1;
                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
            }
            else if (nums[i - 1] < 0)
            {
                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
                g[i] = f[i - 1] + 1;
            }
            ret = max(ret, f[i]);
        }
        return ret;
    }
};

class Solution {
public:
    int getMaxLen(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);
        int ret = 0;
        for (int i = 1; i <= n; i++)
        {
            if (nums[i - 1] > 0)
            {
                f[i] = f[i - 1] + 1;
                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
            }
            else if (nums[i - 1] < 0)
            {
                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
                g[i] = f[i - 1] + 1;
            }
            ret = max(ret, f[i]);
        }
        return ret;
    }
};

class Solution {
public:
    int maxTurbulenceSize(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n), g(n);
        f[0] = g[0] = 1;
        int ret = 1;
        for (int i = 1; i < n; i++)
        {
            f[i] = nums[i] > nums[i - 1] ? g[i - 1] + 1 : 1;
            g[i] = nums[i] < nums[i - 1] ? f[i - 1] + 1 : 1;
            ret = max(ret, max(f[i], g[i]));
        }
        return ret;
    }
};